/*
 * @lc app=leetcode.cn id=915 lang=typescript
 *
 * [915] 分割数组
 */

// @lc code=start
function partitionDisjoint(nums: number[]): number {
  const n = nums.length;
  // 右边每个位置的最小元素
  const minRights = new Array(n).fill(0);
  minRights[n - 1] = nums[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    minRights[i] = Math.min(minRights[i + 1], nums[i]);
  }
  // 左边最大元素
  let maxLeft = 0;
  for (let i = 0; i < n - 1; i++) {
    maxLeft = Math.max(maxLeft, nums[i]);
    if (maxLeft <= minRights[i + 1]) {
      return i + 1;
    }
  }
  return n - 1;
}
// @lc code=end
